package com.qch.edu.lagou.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author qch
 * @Date 2021/7/15
 * 二叉查找树
 * 先序遍历
 * 中序遍历
 * 后序遍历
 * 层序遍历
 */
public class BinaryTree {
    //根节点
    TreeNode root;

    /**
     * 插入数据
     * @param data
     */
    public void insertNode(int data)
    {
        root=insert(root,data);

    }
    public TreeNode insert(TreeNode node,int data)
    {
        //结束条件
        if(node==null)
        {
            return new TreeNode(data);
        }
        if(data<node.data)
        {
            node.leftChild=insert(node.leftChild,data);
        }else if(data>node.data)
        {
            node.rightChild=insert(node.rightChild,data);
        }else //自己
        {
            node.data=data;
        }
        return node;
    }

    /**
     *        10
     *     8      11
     *       9       12
     * 前序遍历，递归->父左右
     * 10 8 9  11 12
     * @param node
     */
    public static void beforeTraver(TreeNode node)
    {
        //结束条件
        if(node==null)
        return;
        System.out.println(node.data);
        beforeTraver(node.leftChild);
        beforeTraver(node.rightChild);
    }
    /**
     *        10
     *     8      11
     *       9       12
     * 中序遍历，递归->左父右
     * 8 9 10 11 12
     * @param node
     */
    public static void midTraver(TreeNode node)
    {
        //结束条件
        if(node==null)
            return;
        midTraver(node.leftChild);
        System.out.println(node.data);
        midTraver(node.rightChild);
    }

    /**
     *        10
     *     8      11
     *       9       12
     * 后序遍历，递归->左右父
     * 9 8 12 11 10
     * @param node
     */
    public static void afterTraver(TreeNode node)
    {
        //结束条件
        if(node==null)
            return;
        afterTraver(node.leftChild);
        afterTraver(node.rightChild);
        System.out.println(node.data);
    }
    /**
     *        10
     *     8      11
     *       9       12
     * 层序遍历
     * 10 8 11 9 12
     * 思路：借助队列实现，父节点先入，出一个节点，进它的左右节点
     * @param root
     */
    public static void levelTraver(TreeNode root)
    {
        //队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //从队尾入队(add满了会抛异常)
        queue.offer(root);
        //队列不为空
        while (!queue.isEmpty())
        {
            //出队  队头出并删除
            TreeNode node = queue.poll();
            System.out.println(node.data);
            //左孩子入队
            if(node.leftChild!=null){
            queue.offer(node.leftChild);}
            //右孩子入队
            if(node.rightChild!=null){
                queue.offer(node.rightChild);}

        }
    }

    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        binaryTree.insertNode(10);
        binaryTree.insertNode(8);
        binaryTree.insertNode(11);
        binaryTree.insertNode(9);
        binaryTree.insertNode(12);
        //断点查看左右孩子
        TreeNode root=binaryTree.root;
        System.out.println("=============前序=====================");
        beforeTraver(root);
        System.out.println("===============中序===================");
        midTraver(root);
        System.out.println("================后序==================");
        afterTraver(root);
        System.out.println("=================广度=================");
        levelTraver(root);
    }
}
